Field of Invention
Various embodiments of the inventive concept of the present disclosure relate to a method for allocating storage space using a buddy allocator, and more particularly, to a method for allocating storage space using a buddy allocator by allocating storage space to blocks of a buddy in response to a block allocation request, and deallocating storage space from a block corresponding to excess storage space not being used.
Description of Related Art
A storage device, such as a memory or a disk, generally manages storage space in units of blocks having a predetermined size for efficient space utilization. To store data in the storage device, an allocation algorithm for allocating storage space of a size desired by a user and retrieving the allocated storage space may be used. In addition, the storage device may use an allocation algorithm for allocating storage space according to blocks in units of multiples. These allocation algorithms may significantly affect system performance.
An allocation manager based on units of blocks may be referred to as a block allocator. A buddy allocator, which is one of the block allocators, may be widely used to efficiently allocate storage space in a memory device. The buddy allocator may be used for allocation of a block device, such as a disk, as well as a memory. A block device allocator may manage allocation and deallocation of disk blocks in a file system.
The basic allocator of the buddy allocator is a binary buddy allocator. The binary buddy allocator may allocate 2n blocks (where n is zero or a positive integer). In other words, when there is a request for allocating three blocks, four blocks are allocated since 22 is the lowest value including the number three. However, storage space allocation using this binary buddy allocator may cause internal fragmentation.